package top.minuy.algorithm.sort.shell;
/**
 * @author Minuy
 * @time 23:34
 * @date 2021/9/28
 */
public class ShellSort {
    private ShellSort() {
    }

    /**
     * 希尔排序
     *
     * @param <E> 可比较泛型支持
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        // h：子数组间隔，从arr.length 到 1
        int h = arr.length / 2;
        while (h >= 1) {  // 最外层循环，拆分子数组

            for (int start = 0; start < h; start++) { // 寻找每个子数组的开头，对每个子数组排序

                // 对[start, start+h, start+2h, ....] 这个子数组排序
                for (int i = start + h; i < arr.length; i += h) { // 选择排序，第二个元素开始
                    E t = arr[i]; // 暂存数值
                    int j = i; //第二个元素开始
                    for (; j - h >= 0 && t.compareTo(arr[j - h]) < 0; j -= h) { // 如果前面的比当前的大
                        arr[j] = arr[j - h]; // 前面的往后移动
                    }
                    // 到了正确位置上
                    arr[j] = t; // 放过来
                }

            }

            h /= 2; // 每次间隔缩短
        }
    }


    /**
     * 希尔排序，循环优化
     *
     * @param <E> 可比较泛型支持
     */
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        // h：子数组间隔，从arr.length 到 1
        int h = arr.length / 2;
        while (h >= 1) {  // 最外层循环，拆分子数组
                // 对[h,n) 这个子数组排序
                for (int i = h; i < arr.length; i ++) { // 选择排序，第二个元素开始
                    E t = arr[i]; // 暂存数值
                    int j = i; //第二个元素开始
                    for (; j - h >= 0 && t.compareTo(arr[j - h]) < 0; j -= h) { // 如果前面的比当前的大
                        arr[j] = arr[j - h]; // 前面的往后移动
                    }
                    // 到了正确位置上
                    arr[j] = t; // 放过来
                }

            h /= 2; // 每次间隔缩短
        }
    }

    /**
     * 希尔排序，优化步长
     *
     * @param <E> 可比较泛型支持
     */
    public static <E extends Comparable<E>> void sort3(E[] arr) {
        // h：子数组间隔，从arr.length 到 1
        int h = 1;
        while(h < arr.length / 2) h = h * 3 + 1;

        while (h >= 1) {  // 最外层循环，拆分子数组
            // 对[h,n) 这个子数组排序
            for (int i = h; i < arr.length; i ++) { // 选择排序，第二个元素开始
                E t = arr[i]; // 暂存数值
                int j = i; //第二个元素开始
                for (; j - h >= 0 && t.compareTo(arr[j - h]) < 0; j -= h) { // 如果前面的比当前的大
                    arr[j] = arr[j - h]; // 前面的往后移动
                }
                // 到了正确位置上
                arr[j] = t; // 放过来
            }

            h /= 3; // 每次间隔缩短
        }
    }


}
